package com.clps.algorithm.chapter08.值和下标之差都在给定的范围内;

import java.util.TreeSet;

/**
 * 给你一个整数数组nums，请判断是否存在两个不同的下标i和j（i和j之差的绝对值不大于给定的k）
 * 使得两个数值nums[i]和nums[j]的差的绝对值不大于给定的t。例如，如果输入数组{1, 2, 3, 1}，
 * k为3，t为0，由于下标0和下标3，它们对应的数字之差的绝对值为0，因此返回true。如果输入数组{1, 5, 9, 1, 5, 9}，k为2，t为3，由于不存在两个下标之差小于等于2的数字它们差的绝对值小于等于3，此时应该返回false。
 *
 */
public class demo1 {
    public static void main(String[] args) {

    }


    public boolean containNearByAlmostDupLicate(int[] nums,int k,int t){
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i <nums.length ; i++) {
            Long lower = set.floor((long) nums[i]);
            if(lower!=null &&lower>=nums[i]-t){
                return true;
            }
            Long upper = set.ceiling((long) nums[i]);
            if(upper!=null && upper<=nums[i]+t){
                return true;
            }
            set.add((long) nums[i]);

            if(i>=k){
                set.remove(nums[i-k]);
            }
        }
        return false;
    }
}
